var FMFPtoPiecewiseBezier = Class.create();
FMFPtoPiecewiseBezier.prototype = {
	initialize: function () {
	},

	/**
	* For a pinned spline, the knots have to be repeated k times
	* (where k is the order), at both the beginning and the end
	*/
	checkPinned: function (k, knots) {

		// Pinned at the start
		for (var i = 1; i < k; ++i) {
			if (knots[i] !== knots[0]) {
				throw Error("not pinned. order: " + k + " knots: " + knots);
			}
		}

		// Pinned at the end
		for (var i = knots.length - 2; i > knots.length - k - 1; --i) {
			if (knots[i] !== knots[knots.length - 1]) {
				throw Error("not pinned. order: " + k + " knots: " + knots);
			}
		}
	},

	multiplicity: function (knots, index) {
		var m = 1;
		for (var i = index + 1; i < knots.length; ++i) {
			if (knots[i] === knots[index]) {
				++m;
			} else {
				break;
			}
		}
		return m;
	},

	/**
	* https://saccade.com/writing/graphics/KnotVectors.pdf
	* A quadratic piecewise Bézier knot vector with seven control points
	* will look like this [0 0 0 1 1 2 2 3 3 3]. In general, in a
	* piecewise Bézier knot vector the first k knots are the same,
	* then each subsequent group of k-1 knots is the same,
	* until you get to the end.
	*/
	computeInsertions: function (k, knots) {
		var objectContext = this;
		var inserts = [];
		var i = k;

		while (i < knots.length - k) {
			var knot = knots[i];
			var m = objectContext.multiplicity(knots, i);

			for (var j = 0; j < k - m - 1; ++j) {
				inserts.push(knot);
			}
			i = i + m;
		}
		return inserts;
	},

	toPiecewiseBezier: function (k, controlPoints, knots) {
		var objectContext = this;
		objectContext.checkPinned(k, knots);
		var insertions = objectContext.computeInsertions(k, knots);
		return insertions.reduce(function (acc, tNew) {
			return objectContext.insertKnot(k, acc.controlPoints, acc.knots, tNew);
		}, {
				controlPoints: controlPoints,
				knots: knots
			});
	},


	/**
 	* Knot insertion is known as "Boehm's algorithm"
 	*
 	* https://math.stackexchange.com/questions/417859/convert-a-b-spline-into-bezier-curves
 	* code adapted from http://preserve.mactech.com/articles/develop/issue_25/schneider.html
 	*/
	insertKnot: function (k, controlPoints, knots, newKnot) {
		var x = knots;
		var b = controlPoints;
		var n = controlPoints.length;
		var i = 0;
		var foundIndex = false;

		for (var j = 0; j < n + k; j++) {
			if (newKnot > x[j] && newKnot <= x[j + 1]) {
				i = j;
				foundIndex = true;
				break;
			}
		}

		if (!foundIndex) {
			throw new Error('invalid new knot');
		}

		var xHat = [];

		for (var j = 0; j < n + k + 1; j++) {
			if (j <= i) {
				xHat[j] = x[j];
			} else if (j === i + 1) {
				xHat[j] = newKnot;
			} else {
				xHat[j] = x[j - 1];
			}
		}

		var alpha;
		var bHat = [];

		for (var j = 0; j < n + 1; j++) {
			if (j <= i - k + 1) {
				alpha = 1;
			} else if (i - k + 2 <= j && j <= i) {
				if (x[j + k - 1] - x[j] === 0) {
					alpha = 0;
				} else {
					alpha = (newKnot - x[j]) / (x[j + k - 1] - x[j]);
				}
			} else {
				alpha = 0;
			}

			if (alpha === 0) {
				bHat[j] = b[j - 1];
			} else if (alpha === 1) {
				bHat[j] = b[j];
			} else {
				bHat[j] = {
					x: (1 - alpha) * b[j - 1].x + alpha * b[j].x,
					y: (1 - alpha) * b[j - 1].y + alpha * b[j].y
				};
			}
		}

		return {
			controlPoints: bHat,
			knots: xHat
		};
	},

	type: 'FMFPtoPiecewiseBezier'
};